<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3968：[WF2013]Harvard</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[WF2013]Harvard</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[WF2013]Harvard</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [WF2013]Harvard                </h1>
                <p>时间限制：20s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>&ldquo;哈佛结构&rdquo;是指一台拥有多个分散内存用于记录指令与数据的计算机。这个术语起源于&ldquo;哈佛马克1号&rdquo;计算机。它由IBM于1944年制造，用纸带记录指令，用继电器来储存数据。</div>
<div>一些最新的单片机使用了&ldquo;哈佛结构&rdquo;（当然没有用纸带和继电器）。数据是由&ldquo;内存库&rdquo;来组织，每个&ldquo;内存库&rdquo;拥有相同数量的数据。每一个访问数据的指令都由2个数控制。一个数a（非0即1）。如果a为0，那么访问的是0号&ldquo;内存库&rdquo;。如果a为1则访问BSR（bank select register &ldquo;内存库&rdquo;选择寄存器）中选择的&ldquo;内存库&rdquo;。另一个数f表示访问该&ldquo;内存库&rdquo;的第f个变量。我们假设每一个指令花费相同的时间运行。另外还有一个可以设定BSR值的命令。</div>
<div>举例来说，假设有4个&ldquo;内存库&rdquo;，每个&ldquo;内存库&rdquo;有8个字节。为了访问位置5（0号&ldquo;内存库&rdquo;第5个变量），我们有两种方法。第一种，使用指令a=0，f=5。第二种，先将BSR的值设为0，然后使用指令a=1，f=5。第一种方法更快，因为它不需要花费时间设置BSR。</div>
<div>现在假设（还是刚才的&ldquo;内存库&rdquo;）我们要访问位置20（2号&ldquo;内存库&rdquo;第4个变量）。现在只有1种方法能够访问。将BSR的值设为2（除非BSR原来就是2），然后用指令a=1，f=4。</div>
<div>一个程序是一个操作的序列，每个操作是：</div>
<div>●一个变量访问操作，写作Vi，i是一个正整数。</div>
<div>●一个循环操作，写作 Rn &lt;program&gt; E，n是一个正整数，&lt;program&gt;是一个任意的程序。这个操作等价于依次执行n遍&lt;program&gt;。</div>
<div>你的工作是决定一个程序最小的运行时间。更确切的说，给出&ldquo;内存库&rdquo;的个数和大小，需要执行的程序，输出为了执行这个程序最小的指令数（包括数据访问指令和设定BSR的指令）。为了完成这个，你必须设定一个变量到&ldquo;内存库&rdquo;的映射，使得这个程序运行时间最短，并且输出这个时间（也就是程序运行的指令数）。开始的时候BSR的值为undefined，直到一条命令显式的设定了它的值。</div>
<div></div>
<p></p></p><hr/><h3>输入格式</h3><p><div>每组输入包含一个case，两行。第一行两个整数b和s，1&le;b&le;13代表&ldquo;内存库&rdquo;的个数，1&le;s&le;13代表每个&ldquo;内存库&rdquo;的大小（即能储存的变量数）。第二行是一个非空程序，最多有1000个元素（每个Rn，Vi，E都算1个元素）。</div>
<div>保证：</div>
<div>在循环Rn中，循环次数1&le;n&le;10^6。</div>
<div>在循环Rn &lt;program&gt; E中, &lt;program&gt;非空。</div>
<div>在数据访问Vi中，1&le;i&le;min(b*s,13)。</div>
<div>程序访问变量的次数不超过10^12次。</div>
<div></div>
<p></p></p><hr/><h3>输出格式</h3><p><div>输出运行该程序最少需要的指令数。</div>
<div></div>
<p></p></p><hr/><h3>样例输入</h3><pre>1 2
V1 V2 V1 V1 V2
</pre><hr/><h3>样例输出</h3><pre>5</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3968" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3968" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>